package com.github.yangyishe.p100;

/**
 * 42. 接雨水
 * https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-interview-150
 * todo 已实现但效率较低
 *
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 *
 *
 * 示例 1：
 * 图片地址: https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png
 *
 *
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * 示例 2：
 *
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 *
 *
 * 提示：
 *
 * n == height.length
 * 1 <= n <= 2 * 104
 * 0 <= height[i] <= 105
 */
public class Problem42 {
    public static void main(String[] args) {
        int[] height={0,1,0,2,1,0,1,3,2,1,2,1};

        Problem42 problem42 = new Problem42();
        int trap = problem42.trap(height);
        System.out.println(trap);
    }

    /**
     * 思路
     * 1. 先从大到小排序, 并且记录每个数据的原索引
     * 2. 从最大数开始逐渐向左右扩展高边界(根据1中获取的排序)
     * 3. 每当扩展一次边界, 对新增加的内部边界进行一次减益计算, 最后获取当次扩展编辑所增加的雨水总量
     * 4. 当边界扩展到边缘, 即结束
     * @param height
     * @return
     */
    public int trap(int[] height) {
        if (height.length<=2) {
            return 0;
        }
        // 1. 带位置排序
        int[][] highest=new int[height.length][2];
        for(int i=0;i<height.length;i++){
            highest[i]=new int[]{height[i],i};
        }
        int[][] temp2=new int[height.length][2];
        sort(highest,0,height.length-1,temp2);

        // 2. 扩展边界
        int leftBndIndex = highest[0][1],
                rightBndIndex=highest[0][1],
                highestIndex=1,
        waterCount=0;
        while(leftBndIndex!=0||rightBndIndex!=height.length-1){
            int[] highestInfo=highest[highestIndex++];
            int h = highestInfo[0];
            int hIndex = highestInfo[1];
            if(hIndex>rightBndIndex){
                // 内部减益计算
                waterCount+=(hIndex-rightBndIndex-1)*h;
                for(int i=rightBndIndex+1;i<hIndex;i++){
                    waterCount-=height[i];
                }

                rightBndIndex=hIndex;
            }
            if(hIndex<leftBndIndex){
                // 内部减益计算
                waterCount+=(leftBndIndex-hIndex-1)*h;
                for(int i=hIndex+1;i<leftBndIndex;i++){
                    waterCount-=height[i];
                }

                leftBndIndex=hIndex;
            }
        }


        return waterCount;
    }

    public void sort(int[][] arr,int leftBoundary,int rightBoundary,int[][] temps){
        if(leftBoundary<rightBoundary){
            int midIndex=(leftBoundary+rightBoundary)/2;
            sort(arr,leftBoundary,midIndex,temps);
            sort(arr,midIndex+1,rightBoundary,temps);
            merge(arr,leftBoundary,rightBoundary,midIndex,temps);
        }
    }

    public void merge(int[][] arr,int leftBoundary,int rightBoundary,int middleBoundary,int[][] temps){
        int leftIndex=leftBoundary;
        int rightIndex=middleBoundary+1;
        int tempCount=0;
        while(leftIndex<=middleBoundary&&rightIndex<=rightBoundary){
            if(arr[leftIndex][0]>=arr[rightIndex][0]){
                temps[tempCount++]=arr[leftIndex++];
            }else{
                temps[tempCount++]=arr[rightIndex++];
            }
        }
        while(leftIndex<=middleBoundary){
            temps[tempCount++]=arr[leftIndex++];
        }
        while(rightIndex<=rightBoundary){
            temps[tempCount++]=arr[rightIndex++];
        }
        if (tempCount >= 0) {
            System.arraycopy(temps, 0, arr, leftBoundary, tempCount);
        }
    }
}
